package com.example.demo.algorithm.leetcode;

import java.util.*;

/**
 * @author liweizhi
 * @date 2020/5/20
 * <p>
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 例:
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 * 请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Q3LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
//        test();
        System.out.println(processMime01("abcabcd"));
    }

    private static void test() {
        // "abcabcbb" -->3
        // au -->2
        // dvdf -->3
        // "pwwkew" -->3
        // "cdd" -->2
        // "abba" -->2
        // abab -->2
        String[] arr = {"abcabcbb", "au", "dvdf", "pwwkew", "cdd", "abba", "abab"};
        for (String str : arr) {
            System.out.println(processMime01(str));
        }
    }

    // 根据高赞回答,稍微优化了点
    static int processMime01(String s) {
        if (s == null) {
            return 0;
        }
        if (s.length() < 2) {
            return s.length();
        }
        int ret = 0;
        int left = 0;
        int right = 0;
        HashMap<Character, Integer> map = new HashMap<>(s.length());
        while (right < s.length()) {
            char charAt = s.charAt(right);
            Integer dupIndex = map.get(charAt);
            // 如果重复了
            if (dupIndex != null) {
                // 每次切换窗口时,判断一下;这样会漏掉最后一个窗口,所以最后返回时再判断一下
                ret = Math.max(right - left, ret);
                // 这里是为了防止abba的情况:即第二个窗口ba,a来的时候其实窗口内是没有a的,所以这时候窗口左侧不用动
                // 1. 判断,如果窗口左侧>重复数据位置 + 1, 那么left不用动了;这样可以不删除map中的元素
                left = Math.max(left, dupIndex + 1);
                // 2. 每次把窗口左侧到重复数据位置的数据溢出
                /*for (int i = left; i <= dupIndex; i++) {
                    map.remove(s.charAt(i));
                    left = dupIndex + 1;
                }*/
            }
            map.put(charAt, right);
            right++;
        }
        return Math.max(right - left, ret);
    }

    // 高赞的解法
    public static int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) return 0;
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        int max = 0;
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            char charAt = s.charAt(right);
            if (map.containsKey(charAt)) {
                // 有重复了,让left直接移动到重复的位置的右面
                // 但是要防止"假重复":因为没有清过map,在abba情况下,第二个窗口中其实没有a,但上面判定为真了
                // 所以取left和dupIndex+1的最大值
//                left = map.get(charAt) + 1;
                left = Math.max(left, map.get(charAt) + 1);
            }
            map.put(charAt, right);
            max = Math.max(max, right - left + 1);
        }
        return max;

    }

    // 官方题解的小优化
    static int processMime02(String s) {
        Set<Character> set = new HashSet<>(s.length());
        int right = 0;
        int ret = 0;
        for (int left = 0; left < s.length(); left++) {
            // 如果没有重复,窗口右边界就一直往右移动
            while (right < s.length() && !set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
            }
            ret = Math.max(ret, right - left);
            // 这里两种可能:1.有重复了,需要从left开始移除,然后窗口左边界右移;2.右边界到头了,以后也就用不着set了,无所谓
            set.remove(s.charAt(left));
        }
        return ret;
    }
}
